package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class ReverseLinkedList {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {

        // 反转链表
        public ListNode reverseList(ListNode head) {
            // 头结点 为空 或者 只有一个节点
            //  直接返回即可 ，不需要反转
            if(head==null||head.next==null){
                return head;
            }
            // 虚拟头结点
            ListNode pre = null;

            ListNode cur;
            // 标识 源链表的下一个节点
            ListNode next = null;

            cur=head;

            next =head.next;


            // 没有到尾节点，则继续找
            while(cur!=null) {
                // 新链表
                cur.next = pre;

                // 新人变旧人
                pre = cur;

                cur = next;

                if(next!=null){
                    next = next.next;
                }
            }


            return pre;

            }

        }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedList().new Solution();
        // put your test code here

        ListNode head = ListNode.createHead(new int[]{1,2,3,4,5});
        ListNode reverseList = solution.reverseList(head);
        
    }
}
